package com.yuren.codecrushlearn.Q5300;

import java.util.Arrays;

/**
 * Created with Intellij IDEA.
 * Description:
 * 优先级队列
 * @author 10204
 * @date 2025-05-13 00:50
 */
public class Q5331 {
    private int[] queue;
    private int size;
    private int capacity;

    public Q5331() {
        queue = new int[8];
        size = 0;
        capacity = 8;
    }

    public void add(int value) {
        if (size == capacity) {
            resize();
        }
        queue[size++] = value;
        swim(size - 1);
    }

    public int poll() {
        if (size == 0) {
            return -1;
        }
        int min = queue[0];
        queue[0] = queue[--size];
        sink(0);
        return min;
    }

    public int peek() {
        if (size == 0) {
            return -1;
        }
        return queue[0];
    }

    private void resize() {
        capacity *= 2;
        queue = Arrays.copyOf(queue, capacity);
    }

    private void swim(int k) {
        while (k > 0 && queue[k] < queue[(k - 1) / 2]) {
            swap(k, (k - 1) / 2);
            k = (k - 1) / 2;
        }
    }

    private void sink(int k) {
        int smallest = k;
        int leftChild = 2 * k + 1;
        int rightChild = 2 * k + 2;

        if (leftChild < size && queue[leftChild] < queue[smallest]) {
            smallest = leftChild;
        }

        if (rightChild < size && queue[rightChild] < queue[smallest]) {
            smallest = rightChild;
        }

        if (smallest != k) {
            swap(k, smallest);
            sink(smallest);
        }
    }

    private void swap(int i, int j) {
        int temp = queue[i];
        queue[i] = queue[j];
        queue[j] = temp;
    }
}
